package arr;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * create by yongli on 2020-07-22 13:12
 */

public class TimeInterval {

    public static void main(String[] args) {
        int[][] edges =  {{1,2,1},{2,3,3},{1,3,100}};
        int n = 3;
        int start =1;
        int end = 3;
        int res = minPath(n,edges,start,end);
        System.out.println(res);
    }

    public static void main3(String[] args) {
        String word = "internationalization";
        String abbr = "i11iz4n";
        String abbr2 = "i12lz4n";
        System.out.println(valid(word, abbr2));
    }

    public static void main2(String[] args) {
        int[][] ints = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] ints1 = {{1, 4}, {4, 5}};
        int[][] res = merge(ints1);
        for (int[] a : res) {
            for (int a1 : a) {
                System.out.println(a1);
            }
        }
    }

    public static int[][] merge(int[][] intervals) {
        // 向前追赶
        int start = 0;
        int len = intervals.length;
        for (int i = 0; i < len; i++) {
            if (i < len - 1) {
                if (intervals[i][1] >= intervals[i + 1][0]) {
                    int max = Math.max(intervals[i][1], intervals[i + 1][1]);
                    intervals[i + 1][0] = intervals[i][0];
                    intervals[i + 1][1] = max;
                    start++;
                }
            }
        }
        int[][] newIntervals = new int[len - start][2];
        System.arraycopy(intervals, start, newIntervals, 0, len - start);
        return newIntervals;
    }

    // 从左向右查找
    public static boolean valid(String word, String abbr) {
        int start = 0;
        int abbrStart = 0;
        int end = word.length();
        while (start < end) {
            StringBuilder sb = new StringBuilder();

            // 第一个字符是数子还是字母
            boolean isDigital = false;
            char ch = abbr.charAt(abbrStart);
            if (48 <= ch && ch < 58) {
                isDigital = true;
            }
            sb.append(ch);
            int i = abbrStart + 1;
            for (; i < abbr.length(); i++) {
                // 数子和字符的简单转换
                char ch2 = abbr.charAt(i);
                if (isDigital) {
                    if (48 <= ch2 && ch2 < 58) {
                        sb.append(ch2);
                    } else {
                        break;
                    }
                } else {
                    if (48 <= ch2 && ch2 < 58) {
                        break;
                    } else {
                        sb.append(ch2);
                    }
                }
            }

            if (isDigital) {
                int pre = Integer.valueOf(new String(sb));
                start += pre;
                abbrStart = i;
                // 是字符
            } else {
                String preStr = new String(sb);
                int len = preStr.length();
                if (preStr.equals(word.substring(start, len + start))) {
                    start += len;
                    abbrStart += len;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    // 最短路径算法，还是使用迪杰特斯拉算法，只不过其算代价的方式不一样。贪心算法思想
    // edges = [ [1，2，1]，[2，3，3]，[1，3，100] ]，
    public static int minPath(int n, int[][] edges, int start, int end) {
        int res = -1;
        // 最少需要计算的距离点数。
        int i = 1;
        // 主要用于存储到已知节点的到start的最短距离，数组索引代表节点索引
        List<Pair<Integer, Integer>> minLens = new ArrayList<>();
        Pair<Integer, Integer> startNode = new Pair<>(start, 0);
        minLens.add(startNode);

        while (true) {
            int minIdx = 0;
            int minLen = 10001;

            // 所有内点到外部的最短距离
            for (Pair<Integer, Integer> pair : minLens) {
                int nodeIdx = pair.getKey();
                int nodeLen = pair.getValue();

                // 某个内点到一个外点的最短距离
                for (int[] edge : edges) {
                    // 和nodeIdx相联系
                    if (edge[0] == nodeIdx && !contains(edge[1],minLens)) {
                        int len = edge[2];
                        int newNodeLen = nodeLen | len;
                        if(newNodeLen < minLen){
                            minLen = newNodeLen;
                            minIdx = edge[1];
                        }

                    }
                    // 相反
                    else if (edge[1] == nodeIdx && !contains(edge[0],minLens)) {
                        int len = edge[2];
                        int newNodeLen = nodeLen | len;
                        if(newNodeLen < minLen){
                            minLen = newNodeLen;
                            minIdx = edge[0];
                        }
                    }
                }
            }

            // 找到最小点
            if(minIdx != 0){
                if(minIdx == end){
                    return minLen;
                }
                Pair<Integer,Integer> pair = new Pair<>(minIdx,minLen);
                minLens.add(pair);
            }else {
                // 没有路径返回
                return -1;
            }
        }

    }

    private static boolean contains(int index, List<Pair<Integer,Integer>> list){
        for(Pair<Integer,Integer> pair:list){
            int node = pair.getKey();
            if(node == index){
                return true;
            }
        }
        return false;
    }

}
